package com.chapter9;

import java.util.Stack;

public class StackOperation {

	public String evaluateRPN(String s){
		String[] rpn=s.split(",");
		Stack<String> rpnStack=new Stack<String>();
		for(String element : rpn){
			if(element.equals("+")){
				double result=Double.parseDouble(rpnStack.pop())+Double.parseDouble(rpnStack.pop());
				rpnStack.push(""+result);
			}
			else if(element.equals("x")){
				double result=Double.parseDouble(rpnStack.pop())*Double.parseDouble(rpnStack.pop());
				rpnStack.push(""+result);
			}
			else if(element.equals("-")){
				double result=-Double.parseDouble(rpnStack.pop())+Double.parseDouble(rpnStack.pop());
				rpnStack.push(""+result);
			}
			else if(element.equals("/")){
				double result=1/Double.parseDouble(rpnStack.pop())*Double.parseDouble(rpnStack.pop());
				rpnStack.push(""+result);
			}
			else
				rpnStack.push(element);
		}
		return rpnStack.peek();
	}
	
	public boolean checkBracketComplement(char open, char close){
		if(open=='{' && close=='}' ||open=='[' && close==']' || open=='(' && close==')')
			return true;
		return false;
	}
	
	public boolean checkBrackets(String s){
		Stack<Character> br=new Stack<Character>();
		br.push(s.charAt(0));
		for(int i=1;i<s.length();i++){
			if(checkBracketComplement(br.peek(),s.charAt(i))){
				br.pop();
			}
			else
				br.push(s.charAt(i));
		}
		return (br.isEmpty());
	}
	
	public int checkBracketCount(String s){
		int count=0;
		Stack<Integer> br=new Stack<Integer>();
		br.push(0);
		for(int i=1;i<s.length();i++){
			if(checkBracketComplement(s.charAt(br.peek()),s.charAt(i))){
				br.pop();
				if(i-br.peek()>count)
					count=i-br.peek();
			}
			else
				br.push(i);
		}
		return count;
	}
	
	public Stack<Integer> getBuildingList(int[] H){
		Stack<Integer> ht=new Stack<Integer>();
		for(int i=0;i<H.length;i++){
			while(!ht.isEmpty() && H[i]>=ht.peek())
				ht.pop();
			ht.push(H[i]);
		}
		return ht;
	}
	
	public void sortStack(Stack<Integer> s){
		sortStackUtil(s);
		System.out.println(s);
	}
	public void sortStackUtil(Stack<Integer> s){
		int top=s.pop();
		sortStackUtil(s);
		insert(top,s);
	}
	
	public void insert(int top, Stack<Integer> s){
		if(s.isEmpty() || s.peek()<=top){
			s.push(top);
			return;
		}
		int temp=s.pop();
		insert(top,s);
		s.push(temp);
	}
	
	
}
